package tree.迭代bfs;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 二叉搜索树中的插入操作701.java
 * @Description https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
 * @createTime 2021年07月05日 19:11:00
 */
public class 二叉搜索树中的插入操作701 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pre = root;
        while (pre != null) {
            if (pre.val < val) {
                //如果值比结果小，并且右节点为null，说明找到比当前节点大的值的插入位置
                if (pre.right == null) {
                    pre.right = new TreeNode(val);
                    break;
                } else {
                    //往右边找，找到比当前节点大的节点
                    pre = pre.right;
                }
            } else {
                //如果值比结果大，并且左节点为null
                if (pre.left == null) {
                    pre.left=new TreeNode(val);
                    break;
                } else {
                    //往左边找，找到比当前节点小的节点
                    pre = pre.left;
                }
            }
        }
        return root;
    }

    /*public TreeNode insertIntoBST2(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val < val) {
            root.right=insertIntoBST2(root.right,val);
        }
        if (root.val > val) {
            root.left=insertIntoBST2(root.left,val);
        }
        return root;
    }*/
}
